package com.algorithm.kth;

import com.algorithm.sort.QuickSort;

import java.util.Arrays;
import java.util.Random;

/**
 * 给出一个数组,求其中第k大的数值;重复数字重复计算顺序
 * <p>
 * 随机选择法:随机选择其中一个数字,对其进行排序(像快排一样把小于它的放在左边,大于的放右边),知道选择的那个数就是目标值
 */
public class RandomSelect {
    public static void main(String[] args) {
        Integer[] arr = {1,4,6,2,5,3,3,234,1,12,35,123,5,213,123,1,2,13,13,7};
        System.out.println(randomSelect(arr, 3));
    }

    /**
     * TODO
     * @param arr
     * @param k
     * @return
     */
    public static final int randomSelect(Integer[] arr, int k) {
        Random random = new Random();
        int[] used = new int[arr.length];
        int targetIndex = arr.length - k;
        int index = QuickSort.partition01(arr, 0, arr.length - 1);
        used[index] = 1;
        while (index != targetIndex){
            //while (used[index] ==1){
                //index = random.nextInt(arr.length);
            //}
            index = QuickSort.partition01Pivot(arr, 0, arr.length - 1,random.nextInt(arr.length));
            System.out.println(Arrays.toString(arr));
            used[index] = 1;
        }
        return arr[index];
    }
}
